//https://leetcode.cn/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/submissions/589198991/
class Solution {
public:
    vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
        int n = edges.size() + 1;
        vector<vector<int>> v(n, vector<int>(n, 0));
        vector<vector<int>> g(n);
        for (auto e : edges) {
            int a = e[0], b = e[1], w = e[2];
            g[a].push_back(b);
            g[b].push_back(a);
            v[a][b] = w;
            v[b][a] = w;
        }
        function<int(int, int, int)> dfs = [&](int i, int fa, int pre) {
            int cnt = 0;
            if (pre % signalSpeed == 0) cnt++;
            for (auto j : g[i]) {
                if (j == fa) continue;
                cnt += dfs(j, i, pre + v[i][j]);
            }
            return cnt;
            };
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            vector<int> num_path;
            for (auto j : g[i]) {
                if (v[i][j] > 0) {
                    int t = dfs(j, i, v[i][j]);
                    if (t > 0) num_path.push_back(t);
                }
            }
            for (int j = 0; j < num_path.size(); j++) {
                for (int k = j + 1; k < num_path.size(); k++) {
                    ans[i] += num_path[j] * num_path[k];
                }
            }
        }
        return ans;
    }
};
